In recent years, as information and communication technologies have become widespread, the importance of information security technologies has been increasing more than ever. Cryptographic techniques are used, as one of these information security technologies, for protecting privacy and confirming communication partners.
However, when attempting to protect something using cryptographic techniques, those who try to break and obtain an encryption appear. For example, a side channel attack that obtains a private key, taking advantage of the fact that time taken for calculation and power consumption in cryptographic process varies in accordance with the value of the private key, is problematic (e.g. Non-Patent Document 1).
A typical side channel attack is a simple power analysis attack (SPA) against the RSA cryptographic scheme (more accurately, an RSA signature using the private key) and against the decryption process of the RSA cryptographic scheme. A main process of the RSA cryptographic scheme is an exponentiation with the private key being an exponent. The exponentiation is realized by repetition of squarings and multiplications. In this case, the multiplication is not performed when a corresponding bit of the private key is “0” and the multiplication is performed only when the corresponding bit of the private key is “1”. Therefore, the SPA obtains the private key from sequence information of the multiplications and squarings which is obtained by waveform judgment of the power consumption.
The SPA may be countered by performing the multiplication even when the bit of the private key is “0”. Two specific conventional methods are described in the following.
In the first method, when the bit of the private key is “0”, “1” is multiplied (e.g. Non-Patent Document 2). Multiplying “1” does not change the result. Therefore, this is the same as not actually performing the multiplication. Furthermore, since the multiplication is performed without depending on the bit value of the private key, the private key cannot be obtained by whether the multiplication is performed or not.
Also, in the second method that counters SPA, the multiplication is performed first, regardless of whether the bit is “0” or “1”. Control is performed such that the result of the multiplication is used only when the bit is “1”, and the result of the multiplication is not used when the bit is “0” (e.g. Patent Document 1 and 2). In this method also, the multiplication is performed without depending on the bit value. Therefore, the private key cannot be obtained by whether the multiplication is performed or not.    Non-Patent Document: The actual threat “Side Channel Analysis” (1), Nikkei Electronics 2005.7. Vol. 18    Non-Patent Document 2: “Power Analysis and Countermeasure of RSA Cryptosystem”, Journal A of the Institute of Electronics, Information and Communication Engineers Vol. J88-A, No. 5 2005    Non-Patent Document 3: P. L. Montgomery, “Modular Multiplication without Trial Division,” Mathematics of Computation, Vol. 44, No. 170, pp. 519-521 (1985)    Patent Document 1: Japanese Laid-open Publication No. 2000-165375    Patent Document 2: U.S. Pat. No. 6,408,075